package name.huzhenbo.java.algorithm.sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * LSD: Least siginificant digit first.
 *
 * Time complexity: r * n (where r is radix number)
 *
 * For each radix, the time complexity is n. (Same as hash)
 */
class RadixSorter implements Sorter {
    private int radixNumber;
    
    private Map<Integer, List<Integer>> holder;

    public RadixSorter(int radixNumber) {
        this.radixNumber = radixNumber;
        holder = new HashMap<Integer, List<Integer>>();
    }

    public int[] go(int[] input) {
        for (int i = 0; i < radixNumber; i++) {
            for (int j : input) {
                putToHolder(j, i);
            }

            int j = 0;
            for (int k = 0; k < 9; k++) {
                if (holder.get(k) != null) {
                    for (int val : holder.get(k)) {
                        input[j++] = val;
                    }
                    holder.remove(k);
                }
            }
        }
        return input;
    }

    private void putToHolder(int element, int radix) {
        int valOfRadix = radix(element, radix);
        if (holder.get(valOfRadix) == null) holder.put(valOfRadix, new ArrayList<Integer>());
        holder.get(valOfRadix).add(element);
    }

    private int radix(int val, int radix) {
        return val / new Double(Math.pow(10, radix)).intValue() % 10;
    }
}
